Construction a geographic information system (GIS) associated with a two-dimensional region representing a surface S, such as a portion of the Earth's surface, often requires decomposition of the region into an assembly of polygonal structures that define and completely cover the region. Given a finite set P of spaced apart points on, and representing, the surface S, one must first determine a convenient array of polygonal structures. Several polygon array construction methods, having different advantages and disadvantages, are available here.
One of the most attractive polygon structures for the set P of points is a set D of Delaunay triangles, with each triangle in the set D having the property that the circle that circumscribes the triangle and passes through its three vertices includes no other point from the set P. Properties of this set D of triangles were discussed by B. Delaunay in "Sur las sphere vide" Bulletin of the Academy of Sciences of the U.S.S.R., VII, Classe Sci. Mat. Nat., pp. 793-800 (1934) and in "Neue Darstellung der geometrischen Krystallographie," Zeitschrift fur Krystallographie, vol. 84 (1932), pp. 109-149. A Delaunay triangulation of a surface is a dual of a Voronoi diagram, obtained by constructing perpendicular bisectors of a selected set of lines joining the points P. These diagrams were discussed by G. Voronoi in "Nouvelles applications des parametres continus a la theorie des formes quadratiques," J. reine und angewandte Mathematik, vol. 133 (1907), pp. 97-178. An approach to Delaunay triangulation is discussed by T-P Fang and L. A. Piegl in "Delaunay Triangulation Using a Uniform Grid," I.E.E.E. Computer Graphics & Applications, vol. 13, no. 3 (May 1993) pp. 36-47.
Another triangulation method, called the "radial sweep method," chooses a central point in the set P and determines the bearing and length of lines to all other points in the set P, beginning at the central point. These lines are sorted based on bearing, and long thin triangles are formed. This triangulation is not equivalent to Delaunay triangulation. The radial sweep method is discussed by Mirante and Weingarten, "The radial sweep algorithm for constructing triangular irregular networks," I.E.E.E. Computer Graphics & Applications, vol. 23 (1982) pp. 11-21.
A third triangulation method, referred to as the "point insertion method," begins with a universal triangle UT that surrounds all the points in the set P and a first point p' within UT that is not in the set P. Each beginning triangle is divided into three other triangles, with a new point (initially p') serving as a vertex of each of these triangles. This division process continues until each point in the set P belongs to a different triangle. This triangular decomposition is then optimized by analyzing quadrilaterals formed by two contiguous triangles with a common triangle edge. The result of this process is also not equivalent to Delaunay triangulation but has the advantage that modification of the resulting triangle structure due to deletion of a point in P, or insertion of a new point into P, is accomplished relatively quickly. In a true Delaunay triangulation, deletion or insertion of a point requires that the whole triangulation procedure be repeated. The point insertion method is discussed by Gold, Chambers and Ramsden in "Automated contour mapping using triangular element data structures and an interpolant over each irregular triangular domain," Proc. of SIGGRAPH, 1977, San Jose, Calif. pp. 170-175.
Some U.S. patents also disclose approaches for decomposition or representation of a topographic surface by a polygonal array. These include U.S. Pat. No. 5,307,292, issued to Brown et al, U.S. Pat. Nos. 5,317,681 and 5,428,717, issued to Glassner, U.S. Pat. No. 5,333,248, issued to Christensen, U.S. Pat. No. 5,367,465, issued to Tazawa et al, U.S. Pat. No. 5,440,674, issued to Park, and U.S. Pat. No. 5,590,248, issued to Zarge et al.
The methods disclosed in these articles and patents have some limitations. In most instances, these methods are not equivalent to the preferred Delaunay triangulation approach. All methods appear to require computation times that are similar to the computation time required for a straightforward Delaunay triangulation, which is often measured in tens of minutes or hours for a realistically complex point set P. What is needed is an approach that approximates Delaunay triangulation but substantially reduces the computation time.